home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / theory / uncertai / uncertai.txt < prev   
Text File  |  1995-04-12  |  14KB  |  289 lines
  1. Newsgroups: comp.ai.games
  2. From: smt@cs.monash.edu.au (Scott M Thomson)
  3. Subject: Uncertainty in AI
  4. Summary: This posting will hopefully publicise Bayesian networks, which provide
  5. Keywords: AI
  6. Date: Fri, 31 Mar 1995 04:56:58 GMT
  7.  
  8.  
  9. Have you ever played peek-a-boo with a small child?  Why is it that it
  10. works?  What is it that engages the child's delight?  Why doesn't it
  11. work with older people?
  12.  
  13. The game of peek-a-boo takes advantage of the limited cognitive
  14. development of the child, when we hide ourselves behind an object the
  15. child's mind no longer registers our presence.  When we pop out from
  16. hiding the child's mind is delirious at the magic of our
  17. rematerialization.
  18.  
  19. A complicated challenge for artificial intelligence since its inception has
  20. been knowledge representation in problems with uncertain domains.  What a 
  21. system can't see is, nonetheless, of possible importance to its reasoning 
  22. mechanisms.  What is unknown is also often still vital to common sense
  23. reasoning.  This posting will hopefully publicise Bayesian networks, which 
  24. provide a formalism for modelling and an inference mechanism for reasoning 
  25. under uncertainty and initiate discussion about uncertainty problems and 
  26. probabilistic reasoning in game AI's.
  27.  
  28. Sun Tzu was a Chinese general who lived approximately 2400 years ago.
  29. His work, ``The Art of War", describes the relationships between
  30. warfare, politics, economics, diplomacy, geography and astronomy.
  31. Such modern generals as Mao Zedung have used his work as a strategic
  32. reference.
  33.  
  34. Sun Tzu's philosophy on war can be summed up in this statement, ``to win one 
  35. hundred victories in one hundred battles is not the acme of skill.  To subdue 
  36. the enemy without fighting is the supreme excellence" [11].  In computer games 
  37. utilising cheats for toughening computer AI there is no skill in a computer 
  38. player's victory.  If a computer player can beat a human on even terms then 
  39. we may start to discuss the skill of the AI designer and any human victory 
  40. is that much more appreciated.
  41.  
  42. The difficulty in representing uncertainty in any game AI is in the vast 
  43. numbers of combinations of actions, strategies and defences available to each 
  44. player.  What we are left with is virtually impossible to represent in tables 
  45. or rules applicable to more than a few circumstances.  Amongst the strategies 
  46. expounded by Sun Tzu are enemy knowledge, concealment and position[11].
  47.  
  48. Enemy knowledge is our most obvious resource.  Another player's units or 
  49. pieces inform us about possible future actions or weaknesses by location, 
  50. numbers and present vectored movement.  They suggest possibilities for 
  51. defensive correction, offensive action and bluffing.  Sun Tzu states that we 
  52. should, ``Analyse the enemy's plans so that we will know his shortcomings as 
  53. well as strong points.  Agitate him in order to ascertain the pattern of his 
  54. movement"[11].
  55.  
  56. Concealment may be viewed as the art of both hiding one's own strategy and 
  57. divining one's opponent's.   By considering our opponent's past history and 
  58. placing our current situation in that context we hope to discover something 
  59. about what is hidden in their mind.  Conversely, our actions must be designed 
  60. to convey as little as possible about the true strength or weakness of our 
  61. positions.
  62.  
  63. The position of units refers to their terrain placement in the game.  Those 
  64. terrains that grant defensive or offensive bonuses to computer players units 
  65. should be utilised to the best advantage.  In addition computer units should 
  66. strike where the enemy is weakest and where the most damage can be inflicted 
  67. at the least loss.  Impaling units on heavily fortified positions for nominal 
  68. gain is best left to real generals in real war and is not a bench mark of 
  69. intelligent behaviour. 
  70.  
  71. To combine everything we need to play a good game in the face of a deceptive 
  72. and hostile opponent is not a trivial task.  Sun Tzu believed, ``as water has 
  73. no constant form, there are no constant conditions in war.  One able to win 
  74. the victory by modifying his tactics in accordance with the enemy situation 
  75. may be called a divine!" [11].  Our aim in designing game AI's is to obtain 
  76. a mechanism for moderate strategic competence, not a program with a claim to 
  77. god-hood.
  78.  
  79. Debate on the mechanism for the representation of uncertainty has settled
  80. into two basic philosophies, extensional and intensional systems [19, p3].  
  81. Extensional systems deal with uncertainty in a context free manner, treating 
  82. uncertainty as a truth value attached to logic rules.  Being context free 
  83. they do not consider interdependencies between their variables.  Intensional 
  84. systems deal with uncertainty in a context sensitive manner.  They try to 
  85. model the interdependencies and relevance relationships of the variables in 
  86. the system.
  87.  
  88. If an extensional system has the rule, 
  89.  
  90.     if A then B with some certainty factor m.
  91.  
  92. and observes A in its database it will infer something about the state of B 
  93. regardless of any other knowledge available to it.  Specifically, on seeing A 
  94. it would update the uncertainty of B by some function of the rule strength 
  95. 'm' [].
  96.  
  97. If an intensional system were to consider the same rule, it would interpret it 
  98. as a conditional probability expression P(B|A) = m [].  What we believe about 
  99. B in this system is dependent on our whole view of the problem and how relevant
  100. information interacts.
  101.  
  102. The difference between these two systems boils down to a trade-off between
  103. semantic accuracy and computational feasibility.  Extensional systems are
  104. computationally efficable but semantically clumsy.  Intensional systems on the
  105. otherhand were thought by some to be computationally intractable even though 
  106. they are semantically clear.
  107.  
  108. Both MYCIN (1984) and PROSPECTOR (1978) are examples of extensional systems.
  109. MUNIN (1987) is an example of an intensional system.
  110.  
  111. MYCIN is an expert system which diagnoses bacterial infections and recommends
  112. prescriptions for their cure.  It uses certainty factor calculus to manipulate
  113. generalised truth values which represent the certainty of particular formulae.
  114. The certainty of a formula is calculated as some function of the certainty of
  115. it subformulae.
  116.  
  117. MUNIN is an expert system which diagnoses neuromuscular disorders in the
  118. upper limbs of humans.  It uses a causal probabilistic network to model the
  119. conditional probabilities for the pathophysiological features of a patient[1].
  120.  
  121. Some of the stochastic infidelity of extensional systems arises in their 
  122. failure to handle predictive or abductive inference.  For instance, there 
  123. is a saying, ``where there's smoke there's fire".  We know that fire causes 
  124. smoke but it is definitely not true that smoke causes fire.  How then do we 
  125. derive the second from the first?  Quite simply, smoke is considered evidence 
  126. for fire, therefore if we see smoke we may be led to believe that there is a 
  127. fire nearby.
  128.  
  129. In an extensional approach to uncertainty it would be necessary to state the
  130. rule that smoke causes fire in order to obtain this inferencing ability.  This
  131. may cause cyclic updating which leads to an over confidence in the belief of 
  132. both fire and smoke, from a simple cigarette.  To avoid this dilemma most 
  133. extensional systems do not allow predictive inferencing.  An example of 
  134. predictive inferencing in a strategic game is the consideration of a player's 
  135. move in reasoning about their overall strategy.
  136.  
  137. Even those authors that support extensional systems as a means for reasoning
  138. under uncertainty acknowledge their semantic failures.
  139. ``There is unfortunately a fundamental conflict between the demands of
  140. computational tractability and semantic expressiveness.  The modularity of
  141. simple rule-based systems aid efficient data update procedures.  However,
  142. severe evidence independence assumptions have to be made for uncertainties to 
  143. be combined and propagated using strictly local calculations"[5].
  144.  
  145. Although computationally feasible these systems lack the stochastic reliability
  146. of plausible reasoning.  THE PROBLEM WITH CERTAINTY FACTORS OR TRUTH VALUES
  147. BEING ATTACHED TO FORMULAE IS THAT CERTAINTY MEASURES VISIBLE FACTS WHEREAS
  148. UNCERTAINTY IS RELATED TO WHAT IS UNSEEN, THAT WHICH IS NOT COVERED BY THE
  149. FORMULAE[].
  150.  
  151. The semantic merits of intensional systems is also the reason for their 
  152. computational complexity.  In the example,
  153.  
  154.                             if P(A|B) = m,
  155.  
  156. we cannot assert anything about B even if given complete knowledge about A.
  157. The rule says only that if A is true and is the only thing that is known to
  158. be relevant to B, then the probability of B is 'm'.  When we discover new
  159. information relevant to B we must revoke our previous beliefs and calculate
  160. P(B|A,K), where K is the new knowledge.  The stochastic fidelity of intensional
  161. systems leaves them impotent unless they can determine the relevance
  162. relationships between the variables in their domain.  It is necessary to use a
  163. formalism for articulating the conditions under which variables are considered
  164. relevant to each other, given what is already known.  Using rule-based systems
  165. we quickly get bogged in the unwieldy consideration of all possible probable
  166. interactions.  This leads to complex and computationally infeasible solutions.
  167.  
  168. Bayesian networks are a mechanism for accomplishing computational efficacy
  169. with a semantically accurate intensional system.  They have been used for such 
  170. purposes as, sensor validation [9], medical diagnoses[1, 2], forecasting [3], 
  171. text understanding [6] and naval vessel classification [7].  
  172.  
  173. The challenge is to encode the knowledge in such a way as to make the
  174. ignorable quickly identifiable and readily accessible.  Bayesian networks
  175. provide a mathematically sound formalism for encoding the dependencies and
  176. independencies in a set of domain variables.  A full discussion is given in
  177. texts devoted to this topic [10].
  178.  
  179. Bayesian networks are directed acyclic graphs in which the nodes represent 
  180. stochastic variables.  These variables can be considered as a set of exhaustive
  181. and mutually exclusive states.  The directed arcs within the structure
  182. represent probabilistic relationships between the variables.  That is, their
  183. conditional dependencies and by default their conditional independencies.
  184.  
  185. We have then, a mechanism for encoding a full joint probability distribution,
  186. graphically, as an appropriate set of marginal and conditional distributions
  187. over the variables involved.  When our graphical representation is sparsely
  188. connected we require a much smaller set of probabilities than would be required
  189. to store a full joint distribution.
  190.  
  191. Each root node within a Bayesian network has a prior probability associated 
  192. with each of its states.  Each other node in the network has a conditional 
  193. probability matrix representing probabilities, for that variable, conditioned 
  194. on the values of its parents.
  195.  
  196. After a network has been initialised according to the prior probabilities of
  197. its root nodes and the conditional probabilities of its other variables, it is
  198. possible to instantiate variables to certain states within the network.  The
  199. network, following instantiation, already has posteriors associated with each
  200. node as a result of the propagation during initialisation. Instantiation leads
  201. to a propagation of probabilities through the network to give posterior beliefs
  202. about the states of the variables represented by the graph.  
  203.  
  204. In conclusion, I am not proposing that Bayesian networks are some god given
  205. solution to all of AI's problems.  It is quite plain that quite a few problems
  206. push the bounds of computational feasibility even for Bayesian networks.  It is
  207. my hope that by posting this I may play some game in the future that "reasons"
  208. in a remotely intelligent way about strategies for victory.  Perhaps 
  209. incorporating the concepts of probabilistic reasoning into a hybrid system 
  210. is a feasible solution to a competent strategic AI.
  211.  
  212. Here is a list of some references I used in my Honours thesis.  Numbers 8 
  213. and 10 are texts devoted to Bayesian Networks.  
  214.  
  215. [1]
  216. Andreassen, S; et al.
  217. ``MUNIN - an Expert EMG Assistant."
  218. {\em Computer-Aided Electromyography and Expert Systems}, 1989.
  219.  
  220. [2]
  221. Berguini, C; Bellazi, R; Spiegelhalter, D.
  222. ``Bayesian Networks Applied to Therapy Monitoring.",
  223. {\em Uncertainty in Artificial Intelligence},
  224. Proceedings of the Seventh Conference (1991) p35.
  225.  
  226. [3]
  227. Dagum, P; Galpher, A; Horvitz, E.
  228. ``Dynamic Network Models for Forcasting."
  229. {\em Uncertainty in Artificial Intelligence},
  230. Proceedings of the Eighth Conference (1992) p41.
  231.  
  232. [4]
  233. Findler, N.
  234. ``Studies in Machine Cognition using th Game of Poker."
  235. {\em Communications of the ACM}, v20, April 1977, p230.
  236.  
  237. [5]
  238. Fox, J; Krause, P.
  239. ``Symbolic Decision Theory and Autonomous Systems."
  240. {\em Uncertainty in Artificial Intelligence},
  241. Proceedings of the Seventh Conference (1991) p103.
  242.  
  243. [6]
  244. Goldman, R; Charniak, E.
  245. ``A Probabilistic Approach to Language Understanding."
  246. {\em Tech Rep CS-90-34}, Dept Comp Sci, Brown University 1990.
  247.  
  248. [7]
  249. Musman, SA; Chang, LW.
  250. ``A Study of Scaling In Bayesian Networks for Ship Classification."
  251. {\em Uncertainty in Artificial Intelligence},
  252. Proceedings of the Ninth Conference (1993) p32.
  253.  
  254. [8]
  255. Neapolitan, RE.
  256. {\em ``Probabilistic Reasoning in Expert Systems, Theory and Algorithms."}
  257. John Wiley and Sons, 1989.
  258.  
  259. [9]
  260. Nicholson, AE; Brady, JM.
  261. ``Sensor Validation using Dynamic Belief Networks."
  262. {\em Uncertainty in Artificial Intelligence},
  263. Proceedings of the Eighth Conference (1992) p207.
  264.  
  265. [10]
  266. Pearl, J.
  267. {\em ``Probabilistic Reasoning in Intelligent Systems, Networks of Plausible Inference."}
  268. Morgan Kaufmann Publishers, Inc, 1988.
  269.  
  270. [11]
  271. Wordsworth Reference.
  272. {\em ``Sun Tzu, The Art of War."}
  273. Sterling Publishing Co Inc, 1990.
  274.  
  275. I hope this has been helpful,
  276.  
  277. Scott Thomson
  278. ###############################################################################
  279. Scott M Thomson                                 \|/  ^^^  \|/
  280. smt@bruce.cs.monash.edu.au                      -O-[/@ @\]-O-
  281.                                                   \ | > | /
  282.                                                   | |___| |
  283.                                                   \ \ U / /
  284.                                                      ---
  285. "Cognito cognito ergo cognito sum cognito"
  286. "I think I think therfore I think I am I think?"
  287. (pardon the grammar)
  288. ###############################################################################
  289.